1 00:00:00,000 --> 00:00:03,690 The following content is provided by MIT OpenCourseWare 2 00:00:03,690 --> 00:00:06,060 under a Creative Commons license. 3 00:00:06,060 --> 00:00:09,510 Additional information about our license and OpenCourseWare 4 00:00:09,510 --> 00:00:11,930 in general is available at OCW.MIT.edu. 5 00:00:11,930 --> 00:00:15,570 6 00:00:15,570 --> 00:00:18,510 PROFESSOR: OK. 7 00:00:18,510 --> 00:00:21,500 So I'll start a little formally. 8 00:00:21,500 --> 00:00:28,160 That this is 18086 in the spring semester of 2006. 9 00:00:28,160 --> 00:00:33,110 And we're lucky to have it videotaped for OpenCourseWare. 10 00:00:33,110 --> 00:00:40,190 So let me begin by remembering the main topics from what you 11 00:00:40,190 --> 00:00:46,590 might call the first half 18085 of fall course. 12 00:00:46,590 --> 00:00:50,690 And then most important to us, so it gets a star, are the 13 00:00:50,690 --> 00:00:54,070 main topics for this course. 14 00:00:54,070 --> 00:00:59,810 So 18.085 began with applied linear algebra. 15 00:00:59,810 --> 00:01:05,330 The discreet equations of mechanics, and physics and 16 00:01:05,330 --> 00:01:07,470 engineering. 17 00:01:07,470 --> 00:01:11,500 And the type of matrices that involved, so we learned what 18 00:01:11,500 --> 00:01:14,400 positive definite matrices are. 19 00:01:14,400 --> 00:01:20,580 Then the center of the course was differential equations, 20 00:01:20,580 --> 00:01:22,180 ordinary differential equations. 21 00:01:22,180 --> 00:01:24,290 So that 1D, partial differential 22 00:01:24,290 --> 00:01:25,620 equations like LaPlace. 23 00:01:25,620 --> 00:01:28,650 That was 2D, with boundary values. 24 00:01:28,650 --> 00:01:32,940 So that lead to systems of equations. 25 00:01:32,940 --> 00:01:36,650 And then the third big topic was Fourier methods. 26 00:01:36,650 --> 00:01:41,760 All of Fourier ideas: series, integrals discreet transform. 27 00:01:41,760 --> 00:01:47,860 So that's like the first half of a course. 28 00:01:47,860 --> 00:01:49,880 Well that's 18085. 29 00:01:49,880 --> 00:01:50,290 OK. 30 00:01:50,290 --> 00:01:52,010 And here we are. 31 00:01:52,010 --> 00:01:58,150 So this course has also three major topics. 32 00:01:58,150 --> 00:02:01,690 The first, the one we start on today is 33 00:02:01,690 --> 00:02:03,620 differential equations. 34 00:02:03,620 --> 00:02:06,580 That start from initial values. 35 00:02:06,580 --> 00:02:10,010 So I'm thinking of the wave equation, where we're given 36 00:02:10,010 --> 00:02:11,650 the displacement of velocity. 37 00:02:11,650 --> 00:02:14,320 The heat equation. 38 00:02:14,320 --> 00:02:17,970 Black-Scholes equation, which comes from finances is a 39 00:02:17,970 --> 00:02:20,820 version of the heat equation. 40 00:02:20,820 --> 00:02:22,430 Ordinary differential equations 41 00:02:22,430 --> 00:02:23,680 that's going to be today. 42 00:02:23,680 --> 00:02:26,570 43 00:02:26,570 --> 00:02:30,500 And non-linear equations, Navier-Stokes ultimately. 44 00:02:30,500 --> 00:02:33,390 But not heavily Navier-Stokes. 45 00:02:33,390 --> 00:02:38,010 So this is where we begin. 46 00:02:38,010 --> 00:02:44,660 And then a second big topic is how to solve. 47 00:02:44,660 --> 00:02:47,190 Because this is course is really applied math and 48 00:02:47,190 --> 00:02:48,820 scientific computing. 49 00:02:48,820 --> 00:02:53,720 The second big topic is how do you solve a large linear 50 00:02:53,720 --> 00:02:56,210 system ax equal b? 51 00:02:56,210 --> 00:03:01,940 Do you do it by direct methods on limitation with 52 00:03:01,940 --> 00:03:03,500 renumbering of nodes. 53 00:03:03,500 --> 00:03:06,780 And there are lots of tricks that makes elimination very 54 00:03:06,780 --> 00:03:08,060 successful. 55 00:03:08,060 --> 00:03:12,220 Or do you do it by iterative methods? 56 00:03:12,220 --> 00:03:14,440 Multi-grid is one. 57 00:03:14,440 --> 00:03:18,820 So this is really modern scientific computing we're 58 00:03:18,820 --> 00:03:20,420 talking about. 59 00:03:20,420 --> 00:03:25,830 We're really at the point where people are computing. 60 00:03:25,830 --> 00:03:31,270 And then the third topic which is a little different is 61 00:03:31,270 --> 00:03:32,840 optimization, minimization. 62 00:03:32,840 --> 00:03:36,630 63 00:03:36,630 --> 00:03:39,000 Linear programming would be one example, 64 00:03:39,000 --> 00:03:41,460 but among many, many. 65 00:03:41,460 --> 00:03:44,690 So that's a major area in applied math. 66 00:03:44,690 --> 00:03:45,100 OK. 67 00:03:45,100 --> 00:03:48,010 So this is our topic differential equations. 68 00:03:48,010 --> 00:03:51,890 And I was asked before the tape started about my own 69 00:03:51,890 --> 00:03:52,780 background. 70 00:03:52,780 --> 00:03:59,200 And my thesis was in this topic. 71 00:03:59,200 --> 00:04:06,010 Because a key question will be stability. 72 00:04:06,010 --> 00:04:08,470 Is the difference method stable. 73 00:04:08,470 --> 00:04:14,160 You'll see that that's a requirement to be any good. 74 00:04:14,160 --> 00:04:18,120 You really have to sort out what, and that usually puts a 75 00:04:18,120 --> 00:04:20,480 limitation on the time step. 76 00:04:20,480 --> 00:04:23,300 So we're going to have a time step. 77 00:04:23,300 --> 00:04:29,220 And it may be limited by the requirement of stability. 78 00:04:29,220 --> 00:04:34,210 And the fact that stability and convergence success of the 79 00:04:34,210 --> 00:04:40,570 method are so intimately linked. 80 00:04:40,570 --> 00:04:44,860 There was s key paper by Lax and Richtmyer 81 00:04:44,860 --> 00:04:47,210 that we'll look at. 82 00:04:47,210 --> 00:04:51,300 It's known now as the Lax Equivalence Theorem, stability 83 00:04:51,300 --> 00:04:52,740 and convergence. 84 00:04:52,740 --> 00:04:53,990 We'll see it in detail. 85 00:04:53,990 --> 00:04:56,630 86 00:04:56,630 --> 00:05:02,020 Actually when I was a grad student by good chance there 87 00:05:02,020 --> 00:05:06,300 was a seminar, and I was asked to report on some paper and it 88 00:05:06,300 --> 00:05:08,050 happened to be that one. 89 00:05:08,050 --> 00:05:12,480 And looking back thank gosh I was lucky. 90 00:05:12,480 --> 00:05:15,730 Because that paper, the Lax-Richtmyer paper with the 91 00:05:15,730 --> 00:05:20,710 Lax Equivalence Theorem set the question of stability. 92 00:05:20,710 --> 00:05:26,870 And then years of effort went into finding tests for 93 00:05:26,870 --> 00:05:31,070 stability -- how do you decide is the method stable. 94 00:05:31,070 --> 00:05:34,440 So we'll see some of that. 95 00:05:34,440 --> 00:05:35,630 OK. 96 00:05:35,630 --> 00:05:40,160 Since then I've worked on other things well wavelets 97 00:05:40,160 --> 00:05:43,380 would be one that relates to Fourier. 98 00:05:43,380 --> 00:05:47,680 And other topics too. 99 00:05:47,680 --> 00:05:49,710 And lots of linear algebra. 100 00:05:49,710 --> 00:05:55,610 But it's a pleasure to look back to the beginning of 101 00:05:55,610 --> 00:05:56,030 [UNINTELLIGIBLE]. 102 00:05:56,030 --> 00:05:58,210 OK. 103 00:05:58,210 --> 00:06:00,890 So that's the OpenCourseWare site which does have the 104 00:06:00,890 --> 00:06:05,740 course outline, and other information about the course. 105 00:06:05,740 --> 00:06:11,920 Some of which I have mentioned informally before the class. 106 00:06:11,920 --> 00:06:17,590 This is our central website with no decimal in 18086, 107 00:06:17,590 --> 00:06:20,880 which will have notes coming up, math 108 00:06:20,880 --> 00:06:25,110 labs things, problems. 109 00:06:25,110 --> 00:06:27,100 That's our content. 110 00:06:27,100 --> 00:06:31,160 It will be the 086 page. 111 00:06:31,160 --> 00:06:31,570 OK. 112 00:06:31,570 --> 00:06:38,130 So that's the course outline in three lines. 113 00:06:38,130 --> 00:06:44,110 And then web page and a handout will give you half a 114 00:06:44,110 --> 00:06:48,190 dozen sub-headings under those. 115 00:06:48,190 --> 00:06:48,740 OK. 116 00:06:48,740 --> 00:06:50,990 So that's the course. 117 00:06:50,990 --> 00:06:56,320 And actually it's the center of scientific computing. 118 00:06:56,320 --> 00:07:00,670 There would be other courses at MIT covering material like 119 00:07:00,670 --> 00:07:06,150 that, because it's just so basic you can't go without it. 120 00:07:06,150 --> 00:07:12,960 All right so now I'm ready to start on the first lecture, 121 00:07:12,960 --> 00:07:16,230 which will be ordinary differential equations. 122 00:07:16,230 --> 00:07:21,150 And I won't always have things so clearly and beautifully 123 00:07:21,150 --> 00:07:25,980 written on the board, but today I'm better organized. 124 00:07:25,980 --> 00:07:30,160 So here's our problem ordinary differential equations. 125 00:07:30,160 --> 00:07:42,060 So we're given initial values u at t equals 0. 126 00:07:42,060 --> 00:07:42,370 OK. 127 00:07:42,370 --> 00:07:44,630 So there's always an initial value here. 128 00:07:44,630 --> 00:07:50,290 The question is what's the equation that makes it evolve? 129 00:07:50,290 --> 00:07:51,020 OK. 130 00:07:51,020 --> 00:07:56,900 So often we'll think in terms of one equation. 131 00:07:56,900 --> 00:07:59,860 The unknown will be u, u of t. 132 00:07:59,860 --> 00:08:06,910 Or in reality there are typically N equations. 133 00:08:06,910 --> 00:08:12,850 N might be 6 or 12 or something in a small problem. 134 00:08:12,850 --> 00:08:17,250 But also N could be very large. 135 00:08:17,250 --> 00:08:20,610 We'll see how easily that happens. 136 00:08:20,610 --> 00:08:21,320 OK. 137 00:08:21,320 --> 00:08:31,735 And often to discuss stability or understand a method and try 138 00:08:31,735 --> 00:08:35,370 it the linear cases the natural one. 139 00:08:35,370 --> 00:08:43,420 So I'll use au with a small a to make us think that we've 140 00:08:43,420 --> 00:08:49,510 got a scalar, or a capital A to indicate we're talking 141 00:08:49,510 --> 00:08:50,760 about a matrix. 142 00:08:50,760 --> 00:08:56,500 143 00:08:56,500 --> 00:08:58,220 So these are linear. 144 00:08:58,220 --> 00:09:01,810 These are likely to be not linear. 145 00:09:01,810 --> 00:09:06,390 But there's a natural match between the number a their 146 00:09:06,390 --> 00:09:10,150 corresponds to the partial of f with respect to u. 147 00:09:10,150 --> 00:09:11,710 And of course we see it. 148 00:09:11,710 --> 00:09:18,230 If that was f then its derivative is indeed a. 149 00:09:18,230 --> 00:09:23,380 And in this matrix case, there would be a Jacobian matrix. 150 00:09:23,380 --> 00:09:30,200 If we have N right hand side, because I have Nu's, and the 151 00:09:30,200 --> 00:09:34,080 matrix that comes in is the derivative of right hand side 152 00:09:34,080 --> 00:09:38,590 and equation i with respect to unknown j. 153 00:09:38,590 --> 00:09:44,290 So it's a N by N matrix, and of course this is the case 154 00:09:44,290 --> 00:09:45,880 where it's a constant. 155 00:09:45,880 --> 00:09:50,390 Yeah I should have said, these are not only linear but 156 00:09:50,390 --> 00:09:52,450 constant coefficients. 157 00:09:52,450 --> 00:09:56,170 So we know of course the solution, it's an exponential 158 00:09:56,170 --> 00:10:01,500 e to the at times u0 the initial bunch. 159 00:10:01,500 --> 00:10:04,350 So we know everything about it. 160 00:10:04,350 --> 00:10:06,460 Nevertheless, it's the best test case 161 00:10:06,460 --> 00:10:10,840 for difference methods. 162 00:10:10,840 --> 00:10:15,880 And let me just comments that we do have to pay attention to 163 00:10:15,880 --> 00:10:19,770 the possibility that a could be complex. 164 00:10:19,770 --> 00:10:25,440 Mostly I'll think of a as a real, and often negative. 165 00:10:25,440 --> 00:10:30,040 Often equation will be stable. 166 00:10:30,040 --> 00:10:35,990 A negative a means that e to the at decreases. 167 00:10:35,990 --> 00:10:40,210 A negative definite matrix, negative eigenvalues, mean 168 00:10:40,210 --> 00:10:44,080 that the matrix exponential is the case. 169 00:10:44,080 --> 00:10:46,670 170 00:10:46,670 --> 00:10:49,560 And if that matrix is symmetric, those eigenvalues 171 00:10:49,560 --> 00:10:54,050 are all real, that's a key case. 172 00:10:54,050 --> 00:11:02,340 Symmetric matrices have real eigenvalues, and they're the 173 00:11:02,340 --> 00:11:07,840 most important most attractive class. 174 00:11:07,840 --> 00:11:14,520 And a negative definite matrix might come from a diffusion 175 00:11:14,520 --> 00:11:21,220 term like second derivative, d second u, dx square. 176 00:11:21,220 --> 00:11:28,630 But a convection term du dx from the first derivative will 177 00:11:28,630 --> 00:11:29,880 not be symmetric. 178 00:11:29,880 --> 00:11:31,800 179 00:11:31,800 --> 00:11:34,620 In fact maybe it'll be anti-symmetric. 180 00:11:34,620 --> 00:11:39,400 It will push the eigenvalues into the complex plane. 181 00:11:39,400 --> 00:11:44,690 And therefore we have to pay attention to the possibility 182 00:11:44,690 --> 00:11:45,980 of complex a. 183 00:11:45,980 --> 00:11:48,520 184 00:11:48,520 --> 00:11:52,020 As you know, the whole point of eigenvalues is that we can 185 00:11:52,020 --> 00:11:58,970 understand matrices to a very large extent by diagonalizing, 186 00:11:58,970 --> 00:12:04,620 by reducing them to N scalar equations with the eigenvalues 187 00:12:04,620 --> 00:12:08,310 as the little a's in those scalar equations. 188 00:12:08,310 --> 00:12:12,110 So anyway that's the set up. 189 00:12:12,110 --> 00:12:15,780 Now I want to say something about methods. 190 00:12:15,780 --> 00:12:19,110 I want to introduce some of the names. 191 00:12:19,110 --> 00:12:22,970 What am I thinking here? 192 00:12:22,970 --> 00:12:27,050 This topic, today's topic, of ordinary differential 193 00:12:27,050 --> 00:12:34,620 equations is not going to last long in 18086. 194 00:12:34,620 --> 00:12:40,850 I might still be discussing it tomorrow. 195 00:12:40,850 --> 00:12:42,880 The variety I mean. 196 00:12:42,880 --> 00:12:45,350 But not much after that. 197 00:12:45,350 --> 00:12:49,650 We'll soon be on to partial differential equations. 198 00:12:49,650 --> 00:12:55,250 So I want to sort of tell you about ordinary differential 199 00:12:55,250 --> 00:13:02,800 equations well in kind of an organized m so that you know 200 00:13:02,800 --> 00:13:06,850 the competing methods. 201 00:13:06,850 --> 00:13:14,780 And also so that you know this key distinction. 202 00:13:14,780 --> 00:13:23,160 Nonstiff is a typical equation, u prime equal minus 203 00:13:23,160 --> 00:13:29,740 4u would be a nonstiff still, completely normal equation. 204 00:13:29,740 --> 00:13:32,320 205 00:13:32,320 --> 00:13:36,680 And for that, those are they the relatively 206 00:13:36,680 --> 00:13:38,630 easy ones to solve. 207 00:13:38,630 --> 00:13:44,950 We can use explicit differences. 208 00:13:44,950 --> 00:13:48,270 And I'll say what that word explicit means. 209 00:13:48,270 --> 00:13:51,810 What I want to do is just like help you 210 00:13:51,810 --> 00:13:54,300 organize in your mind. 211 00:13:54,300 --> 00:13:59,460 So nonstiff are the average every day 212 00:13:59,460 --> 00:14:01,730 differential equations. 213 00:14:01,730 --> 00:14:06,960 For those we can use explicit methods that are fast. 214 00:14:06,960 --> 00:14:10,460 And we can make them accurate. 215 00:14:10,460 --> 00:14:12,610 And explicit means -- 216 00:14:12,610 --> 00:14:16,020 so this is the first meaning -- that I compute the new U, 217 00:14:16,020 --> 00:14:22,230 and I'll use capital U, at time step and n plus 1. 218 00:14:22,230 --> 00:14:26,240 So that's capital U at the new time. 219 00:14:26,240 --> 00:14:30,110 Natural to call that the new time. 220 00:14:30,110 --> 00:14:34,650 Can be computed directly from U at the old time, maybe U at 221 00:14:34,650 --> 00:14:38,450 the time before that, maybe U at the times before that. 222 00:14:38,450 --> 00:14:41,260 223 00:14:41,260 --> 00:14:44,060 In EE terms it's causal. 224 00:14:44,060 --> 00:14:49,500 The new U comes explicitly by some formula that we'll 225 00:14:49,500 --> 00:14:55,150 construct from the previous computations. 226 00:14:55,150 --> 00:14:58,380 It's fast. 227 00:14:58,380 --> 00:15:04,060 Of course, I not only use Un but I used f of Un. 228 00:15:04,060 --> 00:15:11,190 So I should say from Un itself and from f of Un at time tn, 229 00:15:11,190 --> 00:15:15,870 and similarly for earlier times. 230 00:15:15,870 --> 00:15:17,120 You see how fast that is? 231 00:15:17,120 --> 00:15:23,120 Because the only new calculation of f is this one. 232 00:15:23,120 --> 00:15:29,730 The previous step produced Un, and the new step, this step, 233 00:15:29,730 --> 00:15:34,670 we plug it in to find out what the slope is. 234 00:15:34,670 --> 00:15:39,360 And that may be the expensive calculation, because f could 235 00:15:39,360 --> 00:15:44,460 involve all sorts of functions, all sorts of 236 00:15:44,460 --> 00:15:46,080 physical constants. 237 00:15:46,080 --> 00:15:49,170 It can be complicated or not. 238 00:15:49,170 --> 00:15:54,300 but if it is, we only have to do it once here. 239 00:15:54,300 --> 00:15:55,800 that's explicit. 240 00:15:55,800 --> 00:15:57,700 Now what's the opposite? 241 00:15:57,700 --> 00:16:00,590 Implicitly. 242 00:16:00,590 --> 00:16:07,770 So the point about implicit methods is the difference 243 00:16:07,770 --> 00:16:12,870 equation, the formula, involves not just Un plus 1, 244 00:16:12,870 --> 00:16:17,700 the new value, but also the slope at that new value, at 245 00:16:17,700 --> 00:16:20,560 that new unknown value. 246 00:16:20,560 --> 00:16:25,080 So it means that an implicit equation could be non-linear. 247 00:16:25,080 --> 00:16:31,270 Because if f is not linear, then this term could involve 248 00:16:31,270 --> 00:16:34,400 cosines, or exponentials or whatever of the 249 00:16:34,400 --> 00:16:36,010 unknown Un plus 1. 250 00:16:36,010 --> 00:16:40,310 So that way you can't do it as fast. 251 00:16:40,310 --> 00:16:44,960 So this is definitely slower per stiff. 252 00:16:44,960 --> 00:16:50,540 But the advantage and the reason it gets used for stiff 253 00:16:50,540 --> 00:16:56,150 problems is that on stiff problems it will allow a much 254 00:16:56,150 --> 00:16:58,500 larger stiff. 255 00:16:58,500 --> 00:17:03,020 So it's this constant trade-off of 256 00:17:03,020 --> 00:17:06,000 speed versus stability. 257 00:17:06,000 --> 00:17:09,710 These are less stable as we'll see, and we'll get to see what 258 00:17:09,710 --> 00:17:11,320 stability means. 259 00:17:11,320 --> 00:17:16,790 These are slower but more stable implicit methods. 260 00:17:16,790 --> 00:17:18,310 OK. 261 00:17:18,310 --> 00:17:21,080 I didn't get to say what stiff is. 262 00:17:21,080 --> 00:17:22,400 I'll say that in a moment. 263 00:17:22,400 --> 00:17:25,090 264 00:17:25,090 --> 00:17:26,350 OK. 265 00:17:26,350 --> 00:17:29,220 So explicit versus implicit. 266 00:17:29,220 --> 00:17:35,290 Un plus 1 immediately or Un plus 1 only by maybe using 267 00:17:35,290 --> 00:17:41,620 Newton's method to solve an equation, because Un plus 1 268 00:17:41,620 --> 00:17:46,180 appears in a complicated formula. 269 00:17:46,180 --> 00:17:49,460 And we have an equation to solve. 270 00:17:49,460 --> 00:17:50,530 OK. 271 00:17:50,530 --> 00:17:58,870 So now this part of the board begins to 272 00:17:58,870 --> 00:18:01,300 identify different methods. 273 00:18:01,300 --> 00:18:07,760 And I'll follow the same two column system that non-stiff 274 00:18:07,760 --> 00:18:10,090 versus stiff. 275 00:18:10,090 --> 00:18:15,370 So this will be explicit and those will be implicit. 276 00:18:15,370 --> 00:18:16,930 OK. 277 00:18:16,930 --> 00:18:20,350 So that one method that occurs to everybody right away is 278 00:18:20,350 --> 00:18:21,670 Euler's method. 279 00:18:21,670 --> 00:18:25,140 And that will be the first method we'll 280 00:18:25,140 --> 00:18:27,670 construct of course. 281 00:18:27,670 --> 00:18:32,290 So that's the first idea anybody would have. 282 00:18:32,290 --> 00:18:35,450 It has the minimum accuracy. 283 00:18:35,450 --> 00:18:40,500 It's first order, the order of accuracy, will be an issue for 284 00:18:40,500 --> 00:18:42,030 all methods. 285 00:18:42,030 --> 00:18:48,500 And Euler has p equal 1, order p equal 1, first order. 286 00:18:48,500 --> 00:18:50,870 So it's too crude. 287 00:18:50,870 --> 00:18:55,140 I mean if you wanted to track a space station with Euler's 288 00:18:55,140 --> 00:19:01,480 method, you would lose it real fast, or you would have to 289 00:19:01,480 --> 00:19:05,360 take delta t so small that it would be impossible. 290 00:19:05,360 --> 00:19:09,580 So Euler's method is the first one you think of, but not the 291 00:19:09,580 --> 00:19:11,110 one you finish with. 292 00:19:11,110 --> 00:19:16,010 And similarly on the implicit side, backward Euler, we'll 293 00:19:16,010 --> 00:19:21,210 see is again the first implicit method you think of. 294 00:19:21,210 --> 00:19:25,050 But in the end you probably want to do that. 295 00:19:25,050 --> 00:19:26,310 OK. 296 00:19:26,310 --> 00:19:31,780 So those are two specific methods that are easy. 297 00:19:31,780 --> 00:19:35,660 The first ones we'll write down. 298 00:19:35,660 --> 00:19:40,340 Now then comes families of methods, especially these 299 00:19:40,340 --> 00:19:42,560 Adams families. 300 00:19:42,560 --> 00:19:49,920 So Adams-Bashforth is explicit, Adams-Moulton are 301 00:19:49,920 --> 00:19:59,340 implicit, and the coefficients are in books on numerical 302 00:19:59,340 --> 00:20:02,400 analysis and will be on the web. 303 00:20:02,400 --> 00:20:05,140 304 00:20:05,140 --> 00:20:08,480 And I'll say more about them of course. 305 00:20:08,480 --> 00:20:10,770 And see the first ones. 306 00:20:10,770 --> 00:20:13,510 So what Adams-Bashforth how does does it differ from 307 00:20:13,510 --> 00:20:14,930 Adams-Moulton? 308 00:20:14,930 --> 00:20:16,180 OK. 309 00:20:16,180 --> 00:20:20,520 310 00:20:20,520 --> 00:20:22,260 So those are multi-step methods. 311 00:20:22,260 --> 00:20:26,380 Number two was multi-step methods. 312 00:20:26,380 --> 00:20:31,840 To get more accurate we use more old values. 313 00:20:31,840 --> 00:20:35,710 So Adams-Moulton and Adams-Bashforth, or especially 314 00:20:35,710 --> 00:20:40,930 Adams-Bashforth, would use several old values to get the 315 00:20:40,930 --> 00:20:43,290 order of accuracy up high. 316 00:20:43,290 --> 00:20:44,940 OK. 317 00:20:44,940 --> 00:20:49,370 Now this third category. 318 00:20:49,370 --> 00:20:52,290 319 00:20:52,290 --> 00:20:54,750 Of course actually Euler would be the first of the 320 00:20:54,750 --> 00:20:59,380 Adams-Bashforth, and backward Euler might be early in 321 00:20:59,380 --> 00:21:01,240 Adams-Moulton. 322 00:21:01,240 --> 00:21:06,240 Or maybe backward Euler is early in backward differences. 323 00:21:06,240 --> 00:21:08,290 OK. 324 00:21:08,290 --> 00:21:12,490 So what I want to say is Runge-Kutta is like a 325 00:21:12,490 --> 00:21:19,170 different approach to constructing methods. 326 00:21:19,170 --> 00:21:22,270 You might know what some of these already. 327 00:21:22,270 --> 00:21:24,290 And it's a one-step method. 328 00:21:24,290 --> 00:21:27,510 329 00:21:27,510 --> 00:21:39,850 That's a method that just produces by sort of half-steps 330 00:21:39,850 --> 00:21:40,830 you could say. 331 00:21:40,830 --> 00:21:44,620 It gets to Un plus 1. 332 00:21:44,620 --> 00:21:47,210 But it's explicit. 333 00:21:47,210 --> 00:21:53,440 And the code in math lab the code OD45, or maybe I should 334 00:21:53,440 --> 00:22:03,300 say the ODE45, is like the work course of ODEs. 335 00:22:03,300 --> 00:22:05,770 I guess I'm hoping you'll try that. 336 00:22:05,770 --> 00:22:10,720 You'll find ODE45 and I'll try to get on to the web. 337 00:22:10,720 --> 00:22:14,480 But you could just easily discover the syntax to call 338 00:22:14,480 --> 00:22:17,450 it, and apply it to an equation. 339 00:22:17,450 --> 00:22:20,720 Yeah I'll get examples on the web, and 340 00:22:20,720 --> 00:22:22,210 please do the examples. 341 00:22:22,210 --> 00:22:31,490 So the 4 or 5 5 typically means that it use a 4th order 342 00:22:31,490 --> 00:22:34,460 Runge-Kutta, so that's pretty accurate. 343 00:22:34,460 --> 00:22:42,265 To get up to a 4th order means the error after a up a time t 344 00:22:42,265 --> 00:22:47,200 equal 1 say is delta t to the 4th. 345 00:22:47,200 --> 00:22:52,360 So by cutting dealt t in half, you divide the error by 16. 346 00:22:52,360 --> 00:22:55,530 And then it also uses a fifth order one. 347 00:22:55,530 --> 00:22:59,660 348 00:22:59,660 --> 00:23:07,010 And maybe I can point to these words. 349 00:23:07,010 --> 00:23:14,430 What makes ODE45 4 or 5 good, successful. 350 00:23:14,430 --> 00:23:17,080 I mean how does it work? 351 00:23:17,080 --> 00:23:19,560 It slows down or speeds up. 352 00:23:19,560 --> 00:23:23,800 It speeds up when it can, it slows down when it has to. 353 00:23:23,800 --> 00:23:29,550 And speed up means a bigger delta t, slow down means a 354 00:23:29,550 --> 00:23:34,500 smaller delta t for the sake of stability or accuracy. 355 00:23:34,500 --> 00:23:35,670 Yeah. 356 00:23:35,670 --> 00:23:39,870 So if the equation is suddenly doing something, if the 357 00:23:39,870 --> 00:23:44,910 solution is suddenly doing something, you know, important 358 00:23:44,910 --> 00:23:50,670 and quick, then probably at that period delta t will get 359 00:23:50,670 --> 00:23:54,050 reduced automatically by ODE45. 360 00:23:54,050 --> 00:23:57,380 It'll cut it in half, cut in half again, half again. 361 00:23:57,380 --> 00:24:02,280 362 00:24:02,280 --> 00:24:07,710 Every good code is constantly estimating using internal 363 00:24:07,710 --> 00:24:10,730 checks to estimate what error it's making. 364 00:24:10,730 --> 00:24:13,820 365 00:24:13,820 --> 00:24:14,890 About the error. 366 00:24:14,890 --> 00:24:16,560 Just a quick word about the error. 367 00:24:16,560 --> 00:24:21,940 So ODE45 it will, unless you tell it otherwise, the default 368 00:24:21,940 --> 00:24:28,270 accuracy that it will adjust for is relative. 369 00:24:28,270 --> 00:24:33,040 So ODE45 will have a relative accuracy. 370 00:24:33,040 --> 00:24:38,810 So can I just squeeze in a few words of 10 to the minus 3. 371 00:24:38,810 --> 00:24:40,390 It'll shoot for that. 372 00:24:40,390 --> 00:24:45,410 And an absolute accuracy of 10 to the minus 6. 373 00:24:45,410 --> 00:24:50,060 So weird will try to keep the error. 374 00:24:50,060 --> 00:24:52,540 It will plan to keep the error, and it'll tell you if 375 00:24:52,540 --> 00:24:55,980 it has a problem below 10 to the minus 6. 376 00:24:55,980 --> 00:24:58,250 And you could set that differently. 377 00:24:58,250 --> 00:24:59,910 OK. 378 00:24:59,910 --> 00:25:04,900 I hope you experiment a little with ODE45. 379 00:25:04,900 --> 00:25:10,740 And you can either plot the solutions, some exponential. 380 00:25:10,740 --> 00:25:12,220 I mean push it. 381 00:25:12,220 --> 00:25:16,580 Like let delta t be pretty big, and see 382 00:25:16,580 --> 00:25:20,120 where it breaks down. 383 00:25:20,120 --> 00:25:23,780 Well I guess ODE45 is engineered not to break down. 384 00:25:23,780 --> 00:25:28,340 If you try delta t, it'll decide on what 385 00:25:28,340 --> 00:25:30,470 delta t it can do. 386 00:25:30,470 --> 00:25:38,970 So we'll also code, just quickly, some methods by 387 00:25:38,970 --> 00:25:43,420 ourselves, and see for a large delta t what 388 00:25:43,420 --> 00:25:45,140 problems could happen. 389 00:25:45,140 --> 00:25:45,660 OK. 390 00:25:45,660 --> 00:25:48,240 And then backwards. 391 00:25:48,240 --> 00:25:50,500 This says backward differences. 392 00:25:50,500 --> 00:25:56,270 That's the category of implicit methods for stiff 393 00:25:56,270 --> 00:26:01,260 equation, and backward Euler would be the very first. 394 00:26:01,260 --> 00:26:11,900 And ODE15S is the code that is the most used code perhaps for 395 00:26:11,900 --> 00:26:13,850 stiff equations. 396 00:26:13,850 --> 00:26:17,430 And it will do the same thing, it will vary delta t. 397 00:26:17,430 --> 00:26:19,690 It was will vary the order. 398 00:26:19,690 --> 00:26:24,450 So if has to slow down, it may slow. 399 00:26:24,450 --> 00:26:27,715 And if things are happening too quickly, it may change to 400 00:26:27,715 --> 00:26:30,540 a low order, safe, secure method. 401 00:26:30,540 --> 00:26:33,550 When things are, you know, when the satellite is buzzing 402 00:26:33,550 --> 00:26:38,810 out in space and it can take giant steps or it can have 403 00:26:38,810 --> 00:26:44,820 high order accuracy, say in astronomy of course they would 404 00:26:44,820 --> 00:26:53,210 go up to 8th order and high tracking estimating where 405 00:26:53,210 --> 00:27:00,010 stars would go or planets, these will do that 406 00:27:00,010 --> 00:27:03,600 automatically up to a certain point. 407 00:27:03,600 --> 00:27:09,480 And we could write codes, and of course people have, for 408 00:27:09,480 --> 00:27:12,640 Adams-Bashforth and Adams-Moulton varying 409 00:27:12,640 --> 00:27:16,720 delta t varying e. 410 00:27:16,720 --> 00:27:20,190 I guess here's a comment. 411 00:27:20,190 --> 00:27:24,470 If I had given this lecture yesterday, I would have 412 00:27:24,470 --> 00:27:28,670 emphasized number two, Adams-Bashforth and 413 00:27:28,670 --> 00:27:32,610 Adams-Moulton, because books do it and I basically learned 414 00:27:32,610 --> 00:27:37,180 this subject from the major textbooks on ODEs. 415 00:27:37,180 --> 00:27:39,830 416 00:27:39,830 --> 00:27:45,440 But I had a conversation with one of the computational 417 00:27:45,440 --> 00:27:47,890 scientists in the math department, and that changed 418 00:27:47,890 --> 00:27:49,610 the lecture. 419 00:27:49,610 --> 00:27:55,660 Because I learned that although books tend to discuss 420 00:27:55,660 --> 00:28:05,490 those at the Adams method, in practice these 421 00:28:05,490 --> 00:28:06,830 methods three -- 422 00:28:06,830 --> 00:28:08,810 Runge-Kutta and backward differences -- 423 00:28:08,810 --> 00:28:10,760 are the most used. 424 00:28:10,760 --> 00:28:13,950 425 00:28:13,950 --> 00:28:20,760 And that's reflected in the fact that these two major 426 00:28:20,760 --> 00:28:26,750 codes that are available in math lab are in the number 427 00:28:26,750 --> 00:28:27,970 three category. 428 00:28:27,970 --> 00:28:29,610 OK. 429 00:28:29,610 --> 00:28:36,630 So now that's a picture with name but not details right. 430 00:28:36,630 --> 00:28:40,550 I And I haven't even said what stiff means. 431 00:28:40,550 --> 00:28:43,030 So somewhere I've written something about stiff. 432 00:28:43,030 --> 00:28:45,310 Yeah. 433 00:28:45,310 --> 00:28:46,560 OK. 434 00:28:46,560 --> 00:28:51,600 435 00:28:51,600 --> 00:29:02,320 So if I had only e to the minus t in the solution, then 436 00:29:02,320 --> 00:29:06,230 the solution would decay at that rate either the minus t. 437 00:29:06,230 --> 00:29:11,200 That time step would adjust to keep it accurate. 438 00:29:11,200 --> 00:29:17,750 And if I have only e to the minus 99t, then again that of 439 00:29:17,750 --> 00:29:20,810 course is a faster decay, much faster decay. 440 00:29:20,810 --> 00:29:25,450 So the time step would adjust to be much smaller, probably 441 00:29:25,450 --> 00:29:27,350 about 199th or something. 442 00:29:27,350 --> 00:29:35,370 Anyway much smaller to capture within each step the correct 443 00:29:35,370 --> 00:29:39,670 behavior of either the minus 99t and no problem. 444 00:29:39,670 --> 00:29:42,540 So in other words, it's not the minus 99 445 00:29:42,540 --> 00:29:44,020 that makes it stiff. 446 00:29:44,020 --> 00:29:45,990 If it was only the minus 99 -- 447 00:29:45,990 --> 00:29:49,780 in other words if I had a equal minus 99 up there, I 448 00:29:49,780 --> 00:29:52,670 wouldn't call it a stiff equation. 449 00:29:52,670 --> 00:29:57,740 What makes it stiff is the combination here. 450 00:29:57,740 --> 00:30:00,300 451 00:30:00,300 --> 00:30:05,650 You see what's going to happen as time gets anywhere, this is 452 00:30:05,650 --> 00:30:07,540 going to control u of t. 453 00:30:07,540 --> 00:30:10,770 454 00:30:10,770 --> 00:30:18,810 The decay of u of t is going to have that time constant 1. 455 00:30:18,810 --> 00:30:21,190 But this is going to control. 456 00:30:21,190 --> 00:30:28,950 So I'll say but this would control delta t 457 00:30:28,950 --> 00:30:31,550 for explicit methods. 458 00:30:31,550 --> 00:30:37,600 459 00:30:37,600 --> 00:30:41,510 And I just picked minus 99, but it could have been minus 460 00:30:41,510 --> 00:30:44,720 999 or far worse. 461 00:30:44,720 --> 00:30:46,970 So it could be very stiff. 462 00:30:46,970 --> 00:30:54,050 463 00:30:54,050 --> 00:30:57,220 This word stiff and identifying this class of 464 00:30:57,220 --> 00:31:01,460 problems, which now is familiar to everybody who has 465 00:31:01,460 --> 00:31:07,990 to compute, didn't come, you know, with Gaussian and so on. 466 00:31:07,990 --> 00:31:09,840 It came much more recently. 467 00:31:09,840 --> 00:31:13,220 But it's become very important now to 468 00:31:13,220 --> 00:31:15,630 distinguish stiff from non-stiff. 469 00:31:15,630 --> 00:31:18,160 So where does stiff problems arise? 470 00:31:18,160 --> 00:31:25,590 Well you can see how they arise in chemical processes 471 00:31:25,590 --> 00:31:32,140 with very different decay rates, biological processes, 472 00:31:32,140 --> 00:31:36,870 control theory, all sorts of cases where there's a big 473 00:31:36,870 --> 00:31:39,930 dynamic range of rates. 474 00:31:39,930 --> 00:31:47,480 And they also arise in system, because the eigenvalues could 475 00:31:47,480 --> 00:31:51,420 be minus 1 and minus 99. 476 00:31:51,420 --> 00:31:54,740 I can easily create a matrix that has those two 477 00:31:54,740 --> 00:31:56,470 eigenvalues. 478 00:31:56,470 --> 00:31:57,740 So it would be a system. 479 00:31:57,740 --> 00:32:00,080 Let me create such a matrix. 480 00:32:00,080 --> 00:32:05,470 I think probably if I put minus 50s on the diagonal, 481 00:32:05,470 --> 00:32:07,970 that gives trace. 482 00:32:07,970 --> 00:32:10,730 Sum down the diagonal is minus 100. 483 00:32:10,730 --> 00:32:13,020 And that should equal the sum of the eiganvalue. 484 00:32:13,020 --> 00:32:14,660 So, so far so good. 485 00:32:14,660 --> 00:32:17,970 And now if I want these two particular numbers, I could 486 00:32:17,970 --> 00:32:21,250 put 49 here. 487 00:32:21,250 --> 00:32:24,180 So that matrix has those two eigenvalues. 488 00:32:24,180 --> 00:32:27,190 489 00:32:27,190 --> 00:32:32,080 490 00:32:32,080 --> 00:32:36,100 I mean this is the kind of matrix, well you might say ill 491 00:32:36,100 --> 00:32:39,250 conditioned would be a word that you hear for 492 00:32:39,250 --> 00:32:40,730 a matrix like this. 493 00:32:40,730 --> 00:32:43,000 The condition number is the ratio. 494 00:32:43,000 --> 00:32:47,480 So the condition number of this matrix would be the 495 00:32:47,480 --> 00:32:51,250 ratio 99 over 1. 496 00:32:51,250 --> 00:32:54,980 And that condition number is a number that math lab computes 497 00:32:54,980 --> 00:32:57,250 all the time every time you give it a matrix 498 00:32:57,250 --> 00:32:58,260 problem like this. 499 00:32:58,260 --> 00:33:01,350 It estimate, not computes. 500 00:33:01,350 --> 00:33:04,640 Because to compute the condition number requires 501 00:33:04,640 --> 00:33:08,930 solving an eigenvalue problem, and it does not want to take 502 00:33:08,930 --> 00:33:11,160 forever to do that exactly. 503 00:33:11,160 --> 00:33:14,240 But it gets an estimate. 504 00:33:14,240 --> 00:33:19,080 So that's only a moderate condition number of 99. 505 00:33:19,080 --> 00:33:24,700 That's not a disaster, but it makes the point. 506 00:33:24,700 --> 00:33:25,410 OK. 507 00:33:25,410 --> 00:33:27,540 So that's what stiff equations are. 508 00:33:27,540 --> 00:33:28,220 OK. 509 00:33:28,220 --> 00:33:30,780 Now I got one more board prepared. 510 00:33:30,780 --> 00:33:33,230 I won't have this everyday, but let me use 511 00:33:33,230 --> 00:33:35,390 it while I got it. 512 00:33:35,390 --> 00:33:37,810 OK. 513 00:33:37,810 --> 00:33:41,720 It's only prepared in the sense of telling us what we're 514 00:33:41,720 --> 00:33:43,260 going to do. 515 00:33:43,260 --> 00:33:48,280 So this is what's coming: a construction of methods, what 516 00:33:48,280 --> 00:33:50,370 stability is about and what's convergence. 517 00:33:50,370 --> 00:33:54,750 So let me begin, let me get Euler constructed today. 518 00:33:54,750 --> 00:33:56,300 And backward Euler. 519 00:33:56,300 --> 00:34:02,160 So Euler's method will be the most obvious 520 00:34:02,160 --> 00:34:07,420 method, equals f at Un. 521 00:34:07,420 --> 00:34:15,050 So in the model case it's aUn. 522 00:34:15,050 --> 00:34:16,720 So that's Euler. 523 00:34:16,720 --> 00:34:19,560 So that tells us then that we could rewrite it. 524 00:34:19,560 --> 00:34:27,530 Un plus 1 is explicitly 1 plus a dealt t, Un. 525 00:34:27,530 --> 00:34:28,010 Right. 526 00:34:28,010 --> 00:34:33,680 I've moved up the delta t and I moved over the Un, and it's 527 00:34:33,680 --> 00:34:34,930 simple like that. 528 00:34:34,930 --> 00:34:40,460 529 00:34:40,460 --> 00:34:42,580 Let me stay with Euler for a moment. 530 00:34:42,580 --> 00:34:45,920 After n steps, every step just multiplied 531 00:34:45,920 --> 00:34:50,190 by this growth factor. 532 00:34:50,190 --> 00:34:54,180 Let me refer to that as the growth factor even if it's as 533 00:34:54,180 --> 00:34:56,750 I hope smaller than 1. 534 00:34:56,750 --> 00:35:01,590 So Un after and n steps is this thing has 535 00:35:01,590 --> 00:35:03,990 multiplied n times Uo. 536 00:35:03,990 --> 00:35:07,010 537 00:35:07,010 --> 00:35:09,620 And what is the stability now? 538 00:35:09,620 --> 00:35:17,770 Stability is suppose a is negative typically. 539 00:35:17,770 --> 00:35:22,280 That means often we'll just think of that model a 540 00:35:22,280 --> 00:35:26,290 negative, so that the differential equation is 541 00:35:26,290 --> 00:35:27,460 completely stable. 542 00:35:27,460 --> 00:35:28,080 Right. 543 00:35:28,080 --> 00:35:34,550 The e to the 18 with a negative is perfect. 544 00:35:34,550 --> 00:35:37,670 The question is this one perfect? 545 00:35:37,670 --> 00:35:51,710 So stability will be is this number below 1? 546 00:35:51,710 --> 00:35:54,240 That's the test. 547 00:35:54,240 --> 00:35:58,080 Is that we could argue about is probably going to 548 00:35:58,080 --> 00:35:59,110 let it equal 1. 549 00:35:59,110 --> 00:36:04,220 Maybe I'll let it equal. 550 00:36:04,220 --> 00:36:09,000 So 1 plus a delta t smaller than 1. 551 00:36:09,000 --> 00:36:14,160 That'll be the stability requirement for forward Euler. 552 00:36:14,160 --> 00:36:18,190 And what's the a delta t? 553 00:36:18,190 --> 00:36:19,390 What's the boundary? 554 00:36:19,390 --> 00:36:22,600 What's the critical value of a delta t? 555 00:36:22,600 --> 00:36:25,050 Remember a negative. 556 00:36:25,050 --> 00:36:28,290 How negative can it be, or how negative can 557 00:36:28,290 --> 00:36:28,850 this combination be? 558 00:36:28,850 --> 00:36:31,690 You see it's a combination a delta t. 559 00:36:31,690 --> 00:36:40,850 So let me put above here what the stability condition is. 560 00:36:40,850 --> 00:36:45,540 So the stability condition on Euler is going to be -- 561 00:36:45,540 --> 00:36:47,700 so do you see what it is? 562 00:36:47,700 --> 00:36:49,980 How negative can a delta t be? 563 00:36:49,980 --> 00:36:52,730 564 00:36:52,730 --> 00:36:55,910 Go ahead you. 565 00:36:55,910 --> 00:36:57,290 Well let's see. 566 00:36:57,290 --> 00:37:03,710 So if a delta t, this is a negative number, so this is 567 00:37:03,710 --> 00:37:06,840 dragging us down from 1 always. 568 00:37:06,840 --> 00:37:10,790 Right; a delta t is like subtracting away from 1. 569 00:37:10,790 --> 00:37:14,590 So we're here with the 1. 570 00:37:14,590 --> 00:37:17,060 And a delta t is pulling us this way. 571 00:37:17,060 --> 00:37:23,980 And how far, at what point are we going to meet instability? 572 00:37:23,980 --> 00:37:25,480 Yeah. 573 00:37:25,480 --> 00:37:27,480 When we hit minus 1. 574 00:37:27,480 --> 00:37:31,160 This is the 1 plus a delta t that I graphed. 575 00:37:31,160 --> 00:37:33,630 So it starts at 1 with delta t equals 0. 576 00:37:33,630 --> 00:37:35,830 And as I increase delta t, it move this way. 577 00:37:35,830 --> 00:37:37,820 And eventually it hits there. 578 00:37:37,820 --> 00:37:44,560 And the limit will be at a delta t equal minus 2. 579 00:37:44,560 --> 00:37:47,250 580 00:37:47,250 --> 00:37:52,220 Because if it carries me 2 from 1, that 581 00:37:52,220 --> 00:37:54,400 carries me to minus 1. 582 00:37:54,400 --> 00:37:57,960 And if I go further, I'm unstable. 583 00:37:57,960 --> 00:38:00,960 And you could easily check. 584 00:38:00,960 --> 00:38:05,790 That Euler will blow up like crazy if you just go a little 585 00:38:05,790 --> 00:38:07,240 beyond that limit. 586 00:38:07,240 --> 00:38:10,090 Because you're taking powers of a number bigger 587 00:38:10,090 --> 00:38:13,180 than below minus 1. 588 00:38:13,180 --> 00:38:13,690 OK. 589 00:38:13,690 --> 00:38:16,610 So there's the stability limit for Euler. 590 00:38:16,610 --> 00:38:20,480 And that's a pretty unpleasant restriction. 591 00:38:20,480 --> 00:38:23,480 592 00:38:23,480 --> 00:38:28,420 We will have other stability limits. 593 00:38:28,420 --> 00:38:31,440 We'll have some stability limits over here, but we're 594 00:38:31,440 --> 00:38:35,420 looking for numbers better than 2. 595 00:38:35,420 --> 00:38:41,970 This Adams-Bashforth will give us numbers worse than 2. 596 00:38:41,970 --> 00:38:44,780 We'll see those methods first thing next time. 597 00:38:44,780 --> 00:38:46,030 OK. 598 00:38:46,030 --> 00:38:48,800 599 00:38:48,800 --> 00:38:50,840 If I drew a picture then. 600 00:38:50,840 --> 00:38:53,140 Let's see have I got another board here. 601 00:38:53,140 --> 00:38:54,560 Nope. 602 00:38:54,560 --> 00:39:01,200 If I drew a picture of good Euler, so Euler doing its job, 603 00:39:01,200 --> 00:39:07,000 the true solution is decaying like that, and 604 00:39:07,000 --> 00:39:08,830 what does Euler do? 605 00:39:08,830 --> 00:39:13,270 Forward Euler says, it looks here, it looks at the slope, 606 00:39:13,270 --> 00:39:16,820 that's all it knows, it goes maybe that far. 607 00:39:16,820 --> 00:39:22,450 That's a small delta t. 608 00:39:22,450 --> 00:39:24,840 That's an OK method. 609 00:39:24,840 --> 00:39:26,600 You see it's not very accurate of course. 610 00:39:26,600 --> 00:39:30,540 It's lost all the curvature in the solution. 611 00:39:30,540 --> 00:39:34,120 So this was the true solution e to the at. 612 00:39:34,120 --> 00:39:42,080 And this is the 1 plus a delta t to the power well t over 613 00:39:42,080 --> 00:39:45,130 delta t times. 614 00:39:45,130 --> 00:39:48,450 Well this was only one step, so that would just be 1 615 00:39:48,450 --> 00:39:50,230 plus a delta t. 616 00:39:50,230 --> 00:39:55,050 OK. where the bad, the unstable one, if I just try to 617 00:39:55,050 --> 00:40:00,430 draw that, the true solution is e to the at. 618 00:40:00,430 --> 00:40:06,810 I started with that value and the right slope. 619 00:40:06,810 --> 00:40:12,750 But I take two big a time step and I'm below minus 1. 620 00:40:12,750 --> 00:40:15,440 621 00:40:15,440 --> 00:40:22,500 So that was a case of a too large delta t. 622 00:40:22,500 --> 00:40:24,610 OK. 623 00:40:24,610 --> 00:40:29,470 Now I've got one minute left to mention backward Euler. 624 00:40:29,470 --> 00:40:31,850 Well that won't take me long. 625 00:40:31,850 --> 00:40:36,220 I'll just change this to Un plus 1. 626 00:40:36,220 --> 00:40:41,220 So I'm evaluating the slope at the new time. 627 00:40:41,220 --> 00:40:49,360 So this is now backward Euler or implicit Euler. 628 00:40:49,360 --> 00:40:54,140 629 00:40:54,140 --> 00:40:55,230 OK. 630 00:40:55,230 --> 00:40:59,220 So that changes this equation. 631 00:40:59,220 --> 00:41:05,610 Oh let's find out the equation for implicit Euler. 632 00:41:05,610 --> 00:41:06,860 OK. 633 00:41:06,860 --> 00:41:08,600 634 00:41:08,600 --> 00:41:12,150 I only have one more moment, I'll just pop it in this 635 00:41:12,150 --> 00:41:14,830 little corner. 636 00:41:14,830 --> 00:41:18,160 So now here's backward Euler. 637 00:41:18,160 --> 00:41:18,410 Alright. 638 00:41:18,410 --> 00:41:20,970 You can tell me what backward Euler is going to be. 639 00:41:20,970 --> 00:41:27,550 So Un plus 1 minus Un over delta t is aU, n plus 1. 640 00:41:27,550 --> 00:41:30,160 So let me collect the n plus 1's. 641 00:41:30,160 --> 00:41:32,260 So I have one of them. 642 00:41:32,260 --> 00:41:35,060 And then minus a delta t. 643 00:41:35,060 --> 00:41:35,450 Right. 644 00:41:35,450 --> 00:41:40,425 And when I bring it over to the left side, and 645 00:41:40,425 --> 00:41:44,420 here I just have Un. 646 00:41:44,420 --> 00:41:46,280 OK. 647 00:41:46,280 --> 00:41:50,570 So what happens at every step now? 648 00:41:50,570 --> 00:41:53,850 I divide every step as a division by this. 649 00:41:53,850 --> 00:41:56,930 So I could bring this into the denominator. 650 00:41:56,930 --> 00:42:04,380 So Un is that division times U0. 651 00:42:04,380 --> 00:42:09,250 652 00:42:09,250 --> 00:42:11,800 And you see the stability? 653 00:42:11,800 --> 00:42:16,780 What's the size of this growth factor? 654 00:42:16,780 --> 00:42:19,160 Remember I'm thinking of a as a negative. 655 00:42:19,160 --> 00:42:23,440 I'm dealing with a stable differential equation. 656 00:42:23,440 --> 00:42:29,110 And so what's the main point about this growth factor, this 657 00:42:29,110 --> 00:42:30,950 ratio in parentheses? 658 00:42:30,950 --> 00:42:33,820 It is? 659 00:42:33,820 --> 00:42:40,670 If a is a negative, what do I know about that number? 660 00:42:40,670 --> 00:42:45,340 Think of a as minus 2 let's say. 661 00:42:45,340 --> 00:42:50,160 So then I have 1 over 1 plus 2 delta t, because 662 00:42:50,160 --> 00:42:51,870 it's minus a there. 663 00:42:51,870 --> 00:42:55,680 And it's going to be smaller than 1. 664 00:42:55,680 --> 00:42:56,440 Right. 665 00:42:56,440 --> 00:42:58,400 It's going to be stable. 666 00:42:58,400 --> 00:43:02,440 So Euler is actually absolutely 667 00:43:02,440 --> 00:43:04,090 stable, backward Euler. 668 00:43:04,090 --> 00:43:07,970 Backward Euler has this property of a stability. 669 00:43:07,970 --> 00:43:15,480 There is no stability limit on negative a, no problem Or even 670 00:43:15,480 --> 00:43:18,230 pure imaginary a, no problem. 671 00:43:18,230 --> 00:43:19,580 Always stable. 672 00:43:19,580 --> 00:43:25,050 So that shows how implicit methods can be greatly much 673 00:43:25,050 --> 00:43:29,140 more stable than explicit, just by comparing backward to 674 00:43:29,140 --> 00:43:31,670 forward to backward Euler. 675 00:43:31,670 --> 00:43:35,400 But just to remind you the price. 676 00:43:35,400 --> 00:43:39,760 The price is that this equation has to be solved -- 677 00:43:39,760 --> 00:43:43,170 well it wasn't any trouble in linear case. 678 00:43:43,170 --> 00:43:47,400 In the linear case we're just inverting a matrix for a 679 00:43:47,400 --> 00:43:48,500 linear system. 680 00:43:48,500 --> 00:43:53,230 So backward Euler for linear system, big linear system, is 681 00:43:53,230 --> 00:43:58,850 a matrix inversion, well a matrix linear system to solve. 682 00:43:58,850 --> 00:44:02,960 But for a non-linear problem, it's serious work. 683 00:44:02,960 --> 00:44:12,510 And yet you have to do the work if the explicit method 684 00:44:12,510 --> 00:44:14,550 gives you such a small delta t that it's 685 00:44:14,550 --> 00:44:16,680 impossible to go with. 686 00:44:16,680 --> 00:44:17,410 OK. 687 00:44:17,410 --> 00:44:23,240 Thanks for your patience on this first lecture. 688 00:44:23,240 --> 00:44:29,610 So obviously I'm going to have one more discussion of ODEs, 689 00:44:29,610 --> 00:44:35,420 in which we construct these methods, see their stability 690 00:44:35,420 --> 00:44:36,630 and their convergence. 691 00:44:36,630 --> 00:44:39,540 And then we move on to the PDs. 692 00:44:39,540 --> 00:44:40,914